1895C - Torn Lucky Ticket - CodeForces Solution

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <string>
using namespace std;

/*indexed set
    works similar to set ie use insert.

*/
namespace pbds = __gnu_pbds;
typedef pbds::tree<int,pbds::null_type,less<int>,pbds::rb_tree_tag,
    pbds::tree_order_statistics_node_update> indexed_set;


//debugger 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


//standered typedefs
typedef long long ll;
typedef string st;
typedef vector<ll> vec64;
typedef set<ll> set64;
typedef pair<ll,ll>pair64;
typedef bitset<32> bitset32;
typedef bitset<64> bitset64;
// queue [fifo], dqueue [fliflo]

typedef priority_queue <ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<ll> maxheap;  // push() pop() top() empty()
// use UpdateKey(oldkey, newkey) to update key
// use RemoveKey(key) to dlete a key
typedef unordered_map<ll,ll> hashmap64;

# define loopn(i,n) for(ll i = 0;i<n;i++)
# define loop(i,a,b) for(ll i = a;i<b;i++)
# define rloopn(i,n) for(ll i = n;i>-1;i--)
# define rloop(i,a,b) for(ll i = a;i>b;i--)
// sort(arr,arr +len); sorts array of length len st. arr is non-decreasing;
// sort(vec.begin(),vec.end()) -------------------------------------------;
//stable_sort() : provides stable sort -----------------------------------;
//
/* A custom function for comparison to be used while sorting, add this function as 3 rd argument in sort or stable_sort funcs.
auto f = [&](ll i , ll j){
        <add variables and requairesd data if using any other ref data from other data structures than the array/vector to be sorted>
        return <write comparison logic> eg. (ll) ai * sumj > (ll) aj * sumi ;
    };

*/

// Bitmasking Method :
// use __builtin_popcount() for no. of set bits in binary.
// use __builtin_ctz() for no. of trsiling zeros in binary.

void setj(ll &s, ll &j){ // sets j th bit
    s |= (1<<j);
}

void unsetj(ll &s, ll &j){ // unsets j th bit
    s &= ~(1<<j);
}

void togglej(ll &s, ll &j){ // toggles j th bit
    s  ^= (1<<j);
}

ll LSone(ll &s, ll &j){ // gives out the least significalnt bit which is set
    ll T = ((s) & ~(s));
    return __builtin_popcount(T);
}

ll checkj(ll s, ll j){ // checks if jth bit is set : 1 = true , 0 = false
    ll out = s;
    s &= (1<<j);
    return out;
}




//log2(n)
ll Log2n(ll n){
    return (n > 1) ? 1 + Log2n(n / 2) : 0;
}

//GCD
ll gcd(ll x,ll y){
	if(y == 0){
		return x;
	}
	return gcd(y,x % y);
}

// power  ==> calculayes  x^y in log(n) time
ll power(ll x, ll y){
    ll temp;
    if (y == 0)
        return 1;
    temp = power(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else {
        if (y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}

//Float power
float powerf(float x, ll y){
    float temp;
    if (y == 0)
        return 1;
    temp = powerf(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else {
        if (y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}



void solve(){
    ll n;scanf("%lld ",&n);ll arr_one[10] ={0}, arr_two[100] = {0}, arr_three[1000] = {0},arr_f[10000]{0},arr_five[100000] = {0};
    ll thre_break_top[10][19]={0}, thre_break_down[10][19]={0};
    ll for_break_top[10][28]={0}, for_break_down[10][28]={0};
    ll fiv_break_top[10][37]={0}, fiv_break_down[10][37]={0};
    ll fiv_break_top_two[19][28]={0}, fiv_break_down_two[19][28]={0};
    ll arrtsm[19]={0},arrthsm[28]={0},arrforsm[37]={0},arrfivsm[46]={0};
    loopn(i,n){
        ll y;scanf("%lld ",&y);ll cy;
        if(y<10){
            arr_one[y]++;
        }
        else if(y>=10 && y<100){
            arr_two[y]++;
            arrtsm[y%10 + y/10]++;
        }
        else if(y>=100 && y<1000){
            arr_three[y]++;arrthsm[y%10 + (y/10)%10 + y/100]++;
            vec64 v;ll cy = y;
            while(cy>0){
                v.push_back(cy%10);
                cy /=10;
            }
            reverse(v.begin(),v.end());
            thre_break_top[v[0]][v[1] + v[2]]++;
            thre_break_down[v[2]][v[0] + v[1]]++;
        }
        else if(y>=1000 && y<10000){
            arr_f[y]++;arrforsm[y%10 + (y%100)/10 + (y%1000)/100 + y/1000]++;
            vec64 v;ll cy = y;
            while(cy>0){
                v.push_back(cy%10);
                cy /=10;
            }
            reverse(v.begin(),v.end());
            for_break_top[v[0]][v[1] + v[2] + v[3]]++;
            for_break_down[v[3]][v[0] + v[1] + v[2]]++;
        }
        else{
            arr_five[y]++;arrfivsm[y%10 + (y%100)/10 + (y%1000)/100 + (y%10000)/1000 + y/10000]++;
            vec64 v;ll cy = y;
            while(cy>0){
                v.push_back(cy%10);
                cy /=10;
            }
            reverse(v.begin(),v.end());
            fiv_break_top[v[0]][v[1] + v[2] + v[3] + v[4]]++;
            fiv_break_down[v[4]][v[0] + v[1] + v[2] + v[3]]++;
            fiv_break_top_two[v[0] + v[1]][v[2] + v[3] + v[4]]++; 
            fiv_break_down_two[v[3] + v[4]][v[0] + v[1] + v[2]]++;
        }
    }
    ll out = 0;
    loopn(i,10){
        out += arr_one[i] * arr_one[i];//debug(out);
    }
    loopn(i,19){
        out += arrtsm[i] * arrtsm[i];//debug(out);
    }
    loopn(i,28){
        out += arrthsm[i] * arrthsm[i];//debug(out);
    }
    loopn(i,37){
        out += arrforsm[i] * arrforsm[i];//debug(out);
    }
    loopn(i,46){
        out += arrfivsm[i] * arrfivsm[i];//debug(out);
    }
    /*
    loop(i,11,100){
        out += arr_two[i] * arr_two[i];//debug(out);
    }
    loop(i,111,1000){
        out += arr_three[i] * arr_three[i];//debug(out);
    }
    loop(i,1111,10000){
        out += arr_f[i] * arr_f[i];//debug(out);//debug(out);
    }
    loop(i,11111,100000){
        out += arr_five[i] * arr_five[i];//debug(out);//debug(out);
    }*/


    loop(i,1,10){// 1+5 && 5+1;
        loop(j,2,19){
            ll sum= i+j;
            out += arr_one[i] * fiv_break_top_two[j][i+j];
            out += arr_one[i] * fiv_break_down_two[j][i+j];
        }//debug(out,"1 +5");
    }
    loop(i,1,10){// 1+3, 3+1
        loop(j,1,10){
            ll sum= i+j;
            out += arr_one[i] * thre_break_top[j][i+j];
            out += arr_one[i] * thre_break_down[j][i+j];//debug(out,"1 ");
        }//debug(out,"1 +3");
    }
    loop(i,1,10){ // 2+4 && 4+2
        loop(j,11,100){
            ll sum= j%10 + j/10;
            out += arr_two[j] * for_break_top[i][sum +i];
            out += arr_two[j] * for_break_down[i][sum+i];//debug(out);
        }//debug(out,"2 +4");
    }
    loop(i,1,10){//3 + 5 && 5+3
        loop(j,111,1000){
            ll sum= j%10 + (j/10)%10 + j/100;
            out += arr_three[j] * fiv_break_top[i][sum +i];//debug(sum);
            out += arr_three[j] * fiv_break_down[i][sum+i];
        }//debug(out,"3 +5");
    }
    


    printf("%lld\n",out);

    
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	//ll tt;scanf("%lld",&tt);
	//for (ll tc = 0;tc<tt;tc++){
		solve();
	//}
	return 0;
}